package com.example.question.bt.backtrack1;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationTest {

    @Test
    public void testPermute() {
        PermutationTest permutationReview = new PermutationTest();
        List<List<Integer>> list = permutationReview.permute(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
        System.out.println(list);
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }
        dfs(nums, new ArrayList<>(), new boolean[nums.length], res);
        return res;
    }

    private void dfs(int[] nums, List<Integer> path, boolean[] visited, List<List<Integer>> res) {
        // 递归出口
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (visited[i]) {
                continue;
            }
            path.add(nums[i]);
            visited[i] = true;
            // 深度优先遍历
            dfs(nums, path, visited, res);
            visited[i] = false;
            path.remove(path.size() - 1);
        }
    }

    @Test
    public void testPermuteUnique() {
        PermutationTest test = new PermutationTest();
        int[] ints = {1, 2, 1};
        Arrays.sort(ints);
        System.out.println("test.permuteUnique(ints) = " + test.permuteUnique(ints));

    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs1(nums, new boolean[nums.length], new ArrayList<>(), res);
        return res;
    }

    private void dfs1(int[] nums, boolean[] visited, List<Integer> path, List<List<Integer>> res) {
        if (nums.length == path.size()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            // 回溯回来的时候 i-1节点的已经被清除现场 标记为未访问
            if (i >= 1 && nums[i - 1] == nums[i] && !visited[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            visited[i] = true;
            dfs1(nums, visited, path, res);
            visited[i] = false;
            path.remove(path.size() - 1);
        }
    }

    @Test
    public void testCombine() {
        PermutationTest test = new PermutationTest();
        List<List<Integer>> combine = test.combine(4, 2);
        System.out.println(combine);
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        findCombine(n, k, 1, new ArrayList<>(), res);
        return res;
    }

    private void findCombine(int n, int k, int startIndex, List<Integer> combine, List<List<Integer>> res) {
        if (combine.size() == k) {
            res.add(new ArrayList<>(combine));
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            combine.add(i);
            findCombine(n, k, i + 1, combine, res);
            // 回溯的时候 要删除原来的
            combine.remove(combine.size() - 1);
        }
    }

    @Test
    public void testCombinationSum() {
        PermutationTest test = new PermutationTest();
        System.out.println("test.combinationSum(new int[]{2, 3, 6, 7}, 7) = " + test.combinationSum(new int[]{2, 3, 6, 7}, 7));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        findCombinationSum(candidates, 0, target, new ArrayList<>(), ret);
        return ret;
    }

    private void findCombinationSum(int[] candidates, int sum, int target, List<Integer> path, List<List<Integer>> res) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }

        for (int candidate : candidates) {
            path.add(candidate);
            // 下面这三句等价于 findCombinationSum(candidates, sum+candidates[i], target, path, res);
            sum += candidate;
            findCombinationSum(candidates, sum, target, path, res);
            sum -= candidate;
            path.remove(path.size() - 1);
        }
    }

    @Test
    public void testCombinationSum2() {
        PermutationTest test = new PermutationTest();
        System.out.println("test.combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8) = " + test.combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        findCombinationSum2(candidates, 0, 0, target, new ArrayList<>(), ret);
        return ret;
    }

    private void findCombinationSum2(int[] candidates, int sum, int startIndex, int target, List<Integer> path, List<List<Integer>> ret) {
        if (sum == target) {
            ret.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);
            sum += candidates[i];
            findCombinationSum2(candidates, sum, i + 1, target, path, ret);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }


    @Test
    public void testSubsets() {
        PermutationTest test = new PermutationTest();
        System.out.println("test.subsets(new int[]{1, 2, 3}) = " + test.subsets(new int[]{1, 2, 3}));
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        findSubsets(nums, 0, new ArrayList<>(), ret);
        return ret;
    }

    private void findSubsets(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> ret) {
        // 这个遍历完 自动结束
        ret.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            findSubsets(nums, i + 1, path, ret);
            path.remove(path.size() - 1);
        }
    }

    @Test
    public void testSubsetsWithDup() {
        PermutationTest test = new PermutationTest();
        List<List<Integer>> lists = test.subsetsWithDup(new int[]{1, 2, 2});
        System.out.println("lists = " + lists);
    }


    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if (nums == null) {
            return ret;
        }
        Arrays.sort(nums);
        findSubsetsWithDup(nums, 0, new boolean[nums.length], new ArrayList<>(), ret);
        return ret;
    }

    private void findSubsetsWithDup(int[] nums, int startIndex, boolean[] visited, List<Integer> path, List<List<Integer>> ret) {
        ret.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && !visited[i - 1] && nums[i - 1] == nums[i]) {
                continue;
            }
            path.add(nums[i]);
            visited[i] = true;
            findSubsetsWithDup(nums, i + 1, visited, path, ret);
            visited[i] = false;
            path.remove(path.size() - 1);
        }
    }

}
